package learnjava.concur.chapter8;

import datastruct.algorithm.QuickSorter;
import datastruct.algorithm.RandomArray;
import lombok.extern.slf4j.Slf4j;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * forkjoin并行快排
 */
@Slf4j(topic = "P035")
public class P035 {

    public static void main(String[] args) {

        ForkJoinPool pool = new ForkJoinPool(6);
        int[] nums = RandomArray.randomCommon(1,100000,80000);
        int[] nums1 = nums.clone();

        long s2 = System.currentTimeMillis();
        QuickSorter.quickSort(nums1,0,nums1.length-1);
        log.debug("串行耗时：{}",System.currentTimeMillis()-s2);

        long s1 = System.currentTimeMillis();
        pool.invoke(new ParQuickSort(nums,0,nums.length-1));
        log.debug("并行耗时：{}",System.currentTimeMillis()-s1);
    }
}

@Slf4j(topic = "ParQuickSort")
class ParQuickSort extends RecursiveAction {

    private int[] nums;
    private int left, right;

    public ParQuickSort(int[] nums, int left, int right){
        this.nums = nums;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute() {
//        log.info("当前线程：{}，处理范围{}，{}",this,left,right);
        if(left>=right) return;
        int pos = partition(nums,left,right);
        ParQuickSort t1 = new ParQuickSort(nums,left,pos-1);
        ParQuickSort t2 = new ParQuickSort(nums,pos+1,right);
        t1.fork();t2.fork();
        t1.join();t2.join();
    }

    private int partition(int[] nums, int left, int right){
        int pivot = nums[left], i = left, j = right;
        while (i<j){
            while (i<j&&pivot<nums[j]) j--;
            nums[i] = nums[j];
            while (i<j&&pivot>=nums[i]) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        return i;
    }
}
